package  main.java.leetcode.editor.cn;
//2023-06-30 11:05:24
//你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指
//相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。 
// 示例： 
// 输入：
//[
//  [0,2,1,0],
//  [0,1,0,1],
//  [1,1,0,1],
//  [0,1,0,1]
//]
//输出： [1,2,4]
// 
// 提示： 
// 
// 0 < len(land) <= 1000 
// 0 < len(land[i]) <= 1000 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 144 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class PondSizesLcci {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new PondSizesLcci().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

    public int[] pondSizes(int[][] land) {

        List<Integer> ans = new ArrayList<>();
        int m = land.length;
        int n = land[0].length;

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                //找到水域进行dfs遍历
                if(land[i][j] == 0){
                    ans.add(dfs(land,i,j));
                }
            }
        }
        int[] arr = new int[ans.size()];
        for(int i = 0;i<ans.size();i++){
            arr[i] = ans.get(i);
        }
        Arrays.sort(arr);
        return arr;
    }

    private int dfs(int[][] land,int x,int y){
        if(x < 0 || x>=land.length || y<0 || y>=land[0].length || land[x][y] != 0){
            return 0;
        }
        land[x][y] = -1;//遍历过则标记为-1
        int res = 1;
        for(int[] dir : dirs){
            res += dfs(land,x+dir[0],y+dir[1]);
        }

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
